"""
https://leetcode.cn/problems/longest-consecutive-sequence/description/

128. 最长连续序列
已解答
中等
相关标签
premium lock icon
相关企业
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：

输入：nums = [1,0,1,2]
输出：3
 

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

"""

from typing import List
import json
import os


class Solution:
    """
    最容易想到的排序法，时间复杂度为O(nlogn)

    官方解法思路：
    我们会发现其中执行了很多不必要的枚举，
    如果已知有一个 x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，
    因此我们在外层循环的时候碰到这种情况跳过即可。

    那么怎么判断是否跳过呢？
    由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，不然按照上面的分析我们会从 x−1 开始尝试匹配，
    因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
    
    """

    def longestConsecutive(self, nums: List[int]) -> int:
        # 构建num_set
        num_set = set(nums)

        # 遍历数组(本次遍历不需遍历数组，遍历num_set即可)
        max_count=0
        for num in num_set:
            if num-1 not in num_set:
                temp=num
                while temp in num_set:
                    temp+=1
                current_count=temp-num
                max_count=max(max_count,current_count)
        # 如果有前趋数，则跳过
        # 如果没有前趋数，则统计

        return max_count

if __name__=='__main__':
    # 获取当前脚本所在的目录
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, 's128_nums.json')
    with open(file_path, 'r', encoding='utf-8') as f:
        nums = json.load(f)

    s=Solution()
    res=s.longestConsecutive(nums)
    print(res)